1. Technical Field
The present invention relates to stream processing, and more particularly to a system and method for processing arbitrary routing queries.
2. Discussion of Related Art
Consider the problem of simultaneously computing individual routes for an arbitrary number (e.g., millions) of vehicles across an arbitrarily large (e.g., billions of road sections and intersections) road network. As vehicles move along their assigned routes, and road conditions vary, the routes must be periodically updated, resulting into a continuous flow of requests.
One challenge is that the data footprint and the complexity of the routing algorithm is polynomial with the level of details of the road maps. Routing algorithms need increasing amount of processor power and memory resources to function, and cannot be solved using monolithic approaches when dealing with detailed maps, e.g., maps coving the United States of America.
Efficient routing algorithms do exist to solve the routing problem in very large size networks (Dijsktra, Bellman-ford). In the telecommunication industry, distributed extensions of the Dijkstra algorithm have been developed to solve this problem in a scalable manner (e.g., Open Shortest Path First), and similar approaches have been developed for transportation routing services. Those solutions involve multi-tiered or hierarchical network representations for the routing. They approach the problem by decomposing maps into layers, where each layer provides a tradeoff between the scope of the map (size of area covered by map), and the level of details of the map (inversely proportional to the size). For example, they include a backbone area at the core which interconnects border areas at the edge and a top-down algorithm that distributes the routing effort between the various tiers. Lower tiers are responsible for computing route sections (e.g., street level details) to access route sections calculated in the upper-tier (e.g., highways). The disadvantage is that the information becomes summarized in the upper tiers, and mainly includes highways interconnecting larger cities. It thus offers limited and suboptimal routing alternatives in those areas compared to a flat network representation where all routes, small and large, are considered for an end to end routing.
Furthermore, existing routing architectures tend to be service oriented and transactional in nature, and are not suitable for use in adaptive stream processing applications.
Therefore, a need exists for a system and method of stream processing for processing arbitrary routing queries.